package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description: 41. 缺失的第一个正数 {@literal https://leetcode-cn.com/problems/first-missing-positive/}
 * @date: 2020/12/3 0003 15:24
 */
public class J0041_H_FirstMissingPositive {
    /*
    给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数
    提示：
    你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
     */

    /**
     * 1. 确实的数字必定在1 —— len + 1
     * 2. 确定1  在不在数组n内
     * 3. 把数组内超标的数字全部换成1
     * 4. 把每个数字对应的小标的数字置为 - X， 当下一次遍历当 这个数字为负数时候表示这个下标对应的数字是存在的
     * 5.从前往后变量数字（此时当前元素若为负数则表示 当前下标对应的元素是存在的，比如nums[0] == -2:表示正数1是存在的），
     *   此时第一个不为负数的元素对应的下标即为第一个缺失的最小正整数
     */
    public static int firstMissingPositive(int[] nums) {
        int len = nums.length;
        // 1 先判断1 存在不存在
        boolean exist = false;
        for (int i = 0; i < len; i++) {
            if (1 == nums[i]) {
                exist = true;
                break;
            }
        }
        if (!exist) {
            return 1;
        }
        //把当前小标的数字对应的位数置为-1，若当前数位 超标 则 按照1 计算
        for (int i = 0; i < len; i++) {
            if (nums[i] > len || nums[i] <= 0) {
                nums[i] = 1;
            }
        }

        for (int i = 0; i < len; i++) {
            //对应的位置置为负数
            int cur = Math.abs(nums[i]);
            nums[cur - 1] = -Math.abs(nums[cur - 1]);
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;
    }

    public static void main(String[] args) {
        //3
        System.out.println(firstMissingPositive(new int[]{2,1}));
        //3
        System.out.println(firstMissingPositive(new int[]{1, 2, 0}));
        //2
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1}));
        //1
        System.out.println(firstMissingPositive(new int[]{7, 8, 9, 11, 12}));
    }
}
